package cn.chen.算法.十算法;

// 动态规划算法，解决背包问题
public class DynamicProgrammingAlgorithm {

    public static void main(String[] args) {

        int[] w = {1, 4, 3};    // 物品的重量
        int[] val = {1500, 3000, 2000};   // 物品的价格
        int m = 4;    // 背包的容量
        int n = val.length; // 物品的个数

        // 为了记录放入商品的情况，定义一个二维数组，
        int[][] path = new int[n + 1][m + 1];

        // 创建一个二维数组，
        // v[i][j]的含义：表示在前i个物品中能够装入容量为j的背包中的最大价值
        int[][] v = new int[n + 1][m + 1];    // 每一行中的索引 ，表示的是背包的容量

        // 初始化第一行和第一列。默认为0,可以不设置

        // 动态规划处理
        for (int i = 1; i < v.length; i++) {    // 从1 开始 ，不处理第一行

            for (int j = 1; j < v[i].length; j++) { // 从1 开始，不处理第一列

                if (w[i - 1] > j) {   // 物品的重量大于背包的容量
                    v[i][j] = v[i - 1][j];  // 所以物品的数量只能存放表格上一行该列的表格的数据
                } else {

                    // v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);  // val[i-1] w[i-1] 因为i是从1开始，所以这里需要i-1
                    // 为了记录商品存放到背包的情况，我们不能直接使用上面的这个公式，需要使用if else体现该公式。
                    if ((v[i - 1][j]) < (val[i - 1] + v[i - 1][j - w[i - 1]])) {    // 这里的j - w[i-1] 是背包重量减去物品重量，结果从0开始，因为前面的if的限定条件j>=w[i-f]的

                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];        // 这是最优的结果
                        // 把当前情况记录到path
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }
        // 输出最后我们放入的商品
        int i = path.length - 1;        // 行的最大下标
        int j = path[0].length - 1;     // 列的最大下标

        while (i > 0 && j > 0) {    // 从path的最后开始找

            if (path[i][j] == 1) {

                System.out.printf("第%d个商品放入背包中\n", i);
                j -= w[i - 1];      // 放入了一个商品，就将容量减少
            }
            i--;
        }

        // 输出表
        for(int[] ii:v){

            for(int jj:ii){

                System.out.printf("%d\t",jj);
            }
            System.out.println();
        }
    }
}
